package com.ztom.top100;

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

/**
 * 最长连续序列
 * <p>
 * https://leetcode-cn.com/problems/longest-consecutive-sequence/
 *
 * @author ZhangTao
 */
public class Code47LongestConsecutive {

    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int max = 0;
        for (Integer num : set) {
            // 包含前一个数, 当前的数已经被前一个数计算过了, 跳过
            if (set.contains(num - 1)) {
                continue;
            }

            // 不包含前一个数, 从当前的数开始计数
            int count = 1;
            int cur = num;
            while (set.contains(++cur)) {
                // 如果出现连续的下一个数
                count++;
            }
            // 如果连续的数断开, 结算最大连续长度
            max = Math.max(max, count);
        }
        return max;
    }
}
